package everyday3;

/**
 * @Author: Siantar
 * @Date: 2023-07-13-10:28
 * @Description: 1.0
 */
public class T0931 {
    int[] diff = {-1, 0, 1};

    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < 3  ; k++) {
                    if (j + diff[k] >= 0 && j + diff[k] < n){
                        min = Math.min(min, matrix[i + 1][j + diff[k]]);
                    }
                }
                matrix[i][j] += min;
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, matrix[0][i]);
        }
        return res;
    }

}
